package cn.itcast.algorithm;

import cn.itcast.algorithm.entity.BaseHeapBean;

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉堆 - 大顶堆
 * 二叉堆是完全二元树或者是近似完全二元树，按照数据的排列方式可以分为两种：最大堆和最小堆。
 * 最大堆：父结点的键值总是大于或等于任何一个子节点的键值；最小堆：父结点的键值总是小于或等于任何一个子节点的键值。
 * http://www.cnblogs.com/skywang12345/p/3610390.html#a3
 * create by zhangtian3 on 2019/1/4
 */
public class MaxTopHeap {

    public final List<BaseHeapBean> mHeap = new ArrayList<>() ;

    /**
     * 最大堆插入代码 -- 数据上浮
     * 最大堆的向上调整算法（从start开始向上直到0，调整堆）
     *
     * 注：数组实现的堆中，第N个节点左孩子的索引值是（2N+1），有孩子的索引是（2N+2）
     *
     * 参数说明：
     *  start -- 被上调节点的起始位置（一般为数组中最后一个元素的索引）
     *
     * @param start
     */
    protected void filterUp(int start) {
        int c = start ; //当前节点（current）的位置
        int p = (c - 1) /2 ; // 父（parent）节点的位置
        int tmp = mHeap.get(c).getPriority() ;// 当前节点（current）的大小
        BaseHeapBean tmpData = mHeap.get(c) ;

        while(c > 0) {
            int cmp = mHeap.get(p).getPriority() ;// 获取父节点优先级
            if (cmp >= tmp) {
                break;
            }else {
                mHeap.set(c, mHeap.get(p)) ;// 父节点移位，移动到比较之后的当前节点位置
                c = p ;
                p = (p - 1) / 2 ;
            }
        }

        mHeap.set(c, tmpData) ;
    }

    /**
     * 将data插入到二叉堆中
     * insert(data)的作用：将数据data添加到最大堆中。mHeap是动态数组ArrayList对象。
     * 当堆已满的时候，添加失败；否则data添加到最大堆的末尾。然后通过上调算法重新调整数组，使之重新成为最大堆。
     * @param data
     */
    public void insert(BaseHeapBean data) {
        int size = mHeap.size() ;// 大顶堆插入的新元素当前位置就是当前数组的长度[新元素还没有添加进去，不用-1]

        mHeap.add(data) ;// 将“数组”插在表尾
        filterUp(size);// 向上调整堆
    }

    /**
     * 当从最大堆中删除数据时：先删除该数据，然后用最大堆中最后一个的元素插入这个空位；接着，把这个“空位”尽量往上挪，直到剩余的数据变成一个最大堆
     * 执行的步骤不能单纯的用它的字节点来替换；而必须考虑到"替换后的树仍然要是最大堆"！
     *
     * 最大堆的删除 -- 向下调整算法
     * 注：数组实现的堆中，第N个节点的左孩子的索引值是（2N+1）,右孩子的索引值是（2N+2）
     *
     * 参数说明:
     *  start -- 被下调节点的起始位置（一般为0， 表示从第一个开始）
     *  end -- 截至范围（一般为数组中最后一个元素的索引）
     */
    protected  void filterDown(int start, int end) {
        int c = start ; // 当前（current）节点的位置
        int l = 2*c + 1 ; // 左（left）孩子的位置
        int tmp = mHeap.get(c).getPriority() ; // 当前(current)节点的大小
        BaseHeapBean tmpData = mHeap.get(c) ;

        while(l <= end) {
            boolean cmp = mHeap.get(l).getPriority() < mHeap.get(l + 1).getPriority() ;

            // "l"是左孩子 “l+1”是右孩子
            if(l < end && cmp){
                l++ ; // 左右两孩子中选择较大者
            }

            cmp = tmp < mHeap.get(l).getPriority() ;
            if (!cmp) {
                break;// 调整结束
            }else {
                mHeap.set(c, mHeap.get(l)) ;
                c = l ;
                l = 2* l + 1 ;
            }
        }

        mHeap.set(c, tmpData) ;
    }

    /**
     * 删除最大堆中的data
     * 返回值：
     *  0 - 成功
     *  1 - 失败
     * @param data
     * @return
     */
    public int remove(BaseHeapBean data) {
        // 如果“堆”已空，则返回-1
        if(mHeap.isEmpty()){
            return -1 ;
        }

        // 获取data在数组中的索引
        int index = mHeap.indexOf(data) ;
        if(index == -1){
            return -1 ;
        }


        int size = mHeap.size() ;
        mHeap.set(index, mHeap.get(size - 1)) ;// 用最后的一个元素填补
        mHeap.remove(size - 1) ; // 删除最后的元素

        if(mHeap.size() > 1 && index <= (mHeap.size() - 1)){
            filterDown(index, mHeap.size() - 1); // 从index号位置开始自上向下调整为最小堆
        }

        return 0 ;
    }
}
